\chapter{数组}

\section{数组}

\subsection{数组（Array）}

数组能够存储一组类型相同的元素，数组在声明时必须指定它的大小（容量），数组的大小是固定的，无法在运行时动态改变。数组通过下标（index）来访问某一位置上的元素，下标从0开始。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[5] = {3, 6, 8, 2, 4};
\end{lstlisting}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=0.5]
		\draw[-] (0,0) -- (5,0) -- (10,0) -- (15,0) -- (20,0) -- (25,0) -- (25,2.6) -- (20,2.6) -- (15,2.6) -- (10,2.6) -- (5,2.6) -- (0,2.6) -- (0,0);
		\draw[-] (5,0) -- (5,2.6);
		\draw[-] (10,0) -- (10,2.6);
		\draw[-] (15,0) -- (15,2.6);
		\draw[-] (20,0) -- (20,2.6);

		\draw (2.5,1.3) node {arr[0]};
		\draw (7.5,1.3) node {arr[1]};
		\draw (12.5,1.3) node {arr[2]};
		\draw (17.5,1.3) node {arr[3]};
		\draw (22.5,1.3) node {arr[4]};
	\end{tikzpicture}
\end{figure}

如果在声明数组时没有指定数组的大小，那么将根据初始化的元素个数来确定。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[] = {3, 6, 8, 2, 4, 0, 1, 7};
\end{lstlisting}

通过下标可以访问数组中的元素，下标的有效范围是0 $ \sim $ 数组的长度 - 1，如果使用不合法的下标就会导致数组越界。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
cout << arr[0] << endl;		// 3
cout << arr[3] << endl;		// 2
cout << arr[7] << endl;		// 7
\end{lstlisting}

当数组的容量比较大时，可以使用循环来初始化数组。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[10];

for(int i = 0; i < 10; i++) {
	arr[i] = i + 1;
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{查找数据}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	int n;
	cout << "Enter the number of elements: ";
	cin >> n;

	int arr[n];
	cout << "Enter the elements: ";
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int key;
	cout << "Enter the key: ";
	cin >> key;

	bool found = false;
	for (int i = 0; i < n; i++) {
		if (arr[i] == key) {
			found = true;
			break;
		}
	}

	if (found) {
		cout << key << " exists." << endl;
	} else {
		cout << key << " not found!" << endl;
	}

	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter the number of elements: 5
Enter the elements: 4 8 9 2 3
Enter the key: 2
2 exists.
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\mybox{最大值/最小值}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	int num[] = {7, 6, 2, 9, 3, 1, 4, 0, 5, 8};
	int n = sizeof(num) / sizeof(num[0]);
	int max = num[0];
	int min = num[0];

	for (int i = 1; i < n; i++) {
		if (num[i] > max) {
			max = num[i];
		}
		if (num[i] < min) {
			min = num[i];
		}
	}
	
	cout << "Max = " << max << endl;
	cout << "Min = " << min << endl;
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Max = 9
Min = 0
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{for-each}

for-each循环是一种更加简洁的for循环，可以用于遍历访问数组中的每一个元素。\\

\mybox{平方和}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	int arr[5] = {7, 6, 2, 9, 3};
	int sum = 0;
	for (int elem : arr) {
		sum += elem * elem;
	}
	cout << "Square sum = " << sum << endl;

	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Square sum = 179
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{二维数组（2-Dimensional Array）}

二维数组由行和列两个维度组成，行和列的下标同样也都是从0开始。在声明二维数组时，需要指定行和列的大小。二维数组可以看成是由多个一维数组组成的，因此二维数组中的每个元素都是一个一维数组。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
\end{lstlisting}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|}
			\hline
			arr[0][0] & arr[0][1] & arr[0][2] & arr[0][3] \\
			\hline
			arr[1][0] & arr[1][1] & arr[1][2] & arr[1][3] \\
			\hline
			arr[2][0] & arr[2][1] & arr[2][2] & arr[2][3] \\
			\hline
		\end{tabular}
	}
\end{table}

在初始化二维数组时，为了能够更直观地看出二维数组的结构，可以将每一行单独写在一行中。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[3][4] = {
	{1, 2, 3, 4},
	{5, 6, 7, 8},
	{9, 10, 11, 12},
};
\end{lstlisting}

对于容量较大的二维数组，可以通过两层循环进行初始化。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
int arr[3][4];

for(int i = 0; i < 3; i++) {
	for(int j = 0; j < 4; j++) {
		arr[i][j] = 0;
	}
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{矩阵运算}

\begin{align}\nonumber
	\left[\begin{matrix}
			1 & 3 \\
			1 & 0 \\
			1 & 2 \\
		\end{matrix} \right]
	+
	\left[\begin{matrix}
			0 & 0 \\
			7 & 5 \\
			2 & 1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1+0 & 3+0 \\
			1+7 & 0+5 \\
			1+2 & 2+1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1 & 3 \\
			8 & 5 \\
			3 & 3 \\
		\end{matrix} \right]
\end{align}

\begin{align}\nonumber
	\left[\begin{matrix}
			1 & 3 \\
			1 & 0 \\
			1 & 2 \\
		\end{matrix} \right]
	-
	\left[\begin{matrix}
			0 & 0 \\
			7 & 5 \\
			2 & 1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1-0 & 3-0 \\
			1-7 & 0-5 \\
			1-2 & 2-1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1  & 3  \\
			-6 & -5 \\
			-1 & 1  \\
		\end{matrix} \right]
\end{align}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
	int A[3][2] = {
		{1, 3},
		{1, 0},
		{1, 2}
	};
	int B[3][2] = {
		{0, 0},
		{7, 5},
		{2, 1}
	};
	int C[3][2];

	cout << "Matrix Addition" << endl;
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 2; j++) {
			C[i][j] = A[i][j] + B[i][j];
			cout << setw(3) << C[i][j];
		}
		cout << endl;
	}
	
	cout << "Matrix Subtraction" << endl;
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 2; j++) {
			C[i][j] = A[i][j] - B[i][j];
			cout << setw(3) << C[i][j];
		}
		cout << endl;
	}
	
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Matrix Addition
  1  3
  8  5
  3  3
Matrix Subtraction
  1  3
  -6 -5
  -1  1
	\end{verbatim}
\end{tcolorbox}

\newpage

\section{字符串}

\subsection{ASCII}

美国信息交换标准代码ASCII（American Standard Code for Information Interchange）一共定义了128个字符。\\

\begin{longtable}{|c|c|c|c|c|c|c|c|}
	\hline
	\textbf{ASCII} & \textbf{字符} & \textbf{ASCII} & \textbf{字符} & \textbf{ASCII} & \textbf{字符}          & \textbf{ASCII} & \textbf{字符}          \\
	\hline
	0              & NUT           & 32             & (space)       & 64             & @                      & 96             & \lstinline|`| \\
	\hline
	1              & SOH           & 33             & !             & 65             & A                      & 97             & a                      \\
	\hline
	2              & STX           & 34             & \text{"}      & 66             & B                      & 98             & b                      \\
	\hline
	3              & ETX           & 35             & \#            & 67             & C                      & 99             & c                      \\
	\hline
	4              & EOT           & 36             & \$            & 68             & D                      & 100            & d                      \\
	\hline
	5              & ENQ           & 37             & \%            & 69             & E                      & 101            & e                      \\
	\hline
	6              & ACK           & 38             & \&            & 70             & F                      & 102            & f                      \\
	\hline
	7              & BEL           & 39             & \text{'}      & 71             & G                      & 103            & g                      \\
	\hline
	8              & BS            & 40             & (             & 72             & H                      & 104            & h                      \\
	\hline
	9              & HT            & 41             & )             & 73             & I                      & 105            & i                      \\
	\hline
	10             & LF            & 42             & *             & 74             & J                      & 106            & j                      \\
	\hline
	11             & VT            & 43             & +             & 75             & K                      & 107            & k                      \\
	\hline
	12             & FF            & 44             & ,             & 76             & L                      & 108            & l                      \\
	\hline
	13             & CR            & 45             & -             & 77             & M                      & 109            & m                      \\
	\hline
	14             & SO            & 46             & .             & 78             & N                      & 110            & n                      \\
	\hline
	15             & SI            & 47             & /             & 79             & O                      & 111            & o                      \\
	\hline
	16             & DLE           & 48             & 0             & 80             & P                      & 112            & p                      \\
	\hline
	17             & DC1           & 49             & 1             & 81             & Q                      & 113            & q                      \\
	\hline
	18             & DC2           & 50             & 2             & 82             & R                      & 114            & r                      \\
	\hline
	19             & DC3           & 51             & 3             & 83             & S                      & 115            & s                      \\
	\hline
	20             & DC4           & 52             & 4             & 84             & T                      & 116            & t                      \\
	\hline
	21             & NAK           & 53             & 5             & 85             & U                      & 117            & u                      \\
	\hline
	22             & SYN           & 54             & 6             & 86             & V                      & 118            & v                      \\
	\hline
	23             & TB            & 55             & 7             & 87             & W                      & 119            & w                      \\
	\hline
	24             & CAN           & 56             & 8             & 88             & X                      & 120            & x                      \\
	\hline
	25             & EM            & 57             & 9             & 89             & Y                      & 121            & y                      \\
	\hline
	26             & SUB           & 58             & :             & 90             & Z                      & 122            & z                      \\
	\hline
	27             & ESC           & 59             & ;             & 91             & [                      & 123            & \{                     \\
			\hline
	28             & FS            & 60             & <             & 92             & $ \backslash $         & 124            & |                      \\
			\hline
	29             & GS            & 61             & =             & 93             & ]                      & 125            & \}                     \\
	\hline
	30             & RS            & 62             & >             & 94             & \lstinline|^| & 126            & \lstinline|~| \\
	\hline
	31             & US            & 63             & ?             & 95             & \_                     & 127            & DEL                    \\
	\hline
\end{longtable}

\vspace{0.5cm}

\mybox{ASCII}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	for(int i = 0; i < 128; i++) {
		cout << i << " - " << (char)i << endl;
	}
	return 0;
}
\end{lstlisting}

\vspace{0.5cm}

\subsection{字符串（String）}

字符数组通常被称为字符串，字符串有两种初始化的方式。一种与普通数组的初始化类似，逐个写出每一个字符，最后需要手动添加$ \backslash $0字符，表示字符串的结束符；另一种是直接使用双引号，这种写法无需手动添加$ \backslash $0。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
char str[8] = {'p', 'r', 'o', 'g', 'r', 'a', 'm', '\0'};
char str[8] = "program";
\end{lstlisting}

$ \backslash $0占一个字符的大小，因此在设置字符串的大小时需要考虑$ \backslash $0。\\

使用cin和cin.getline()都可以用于读取字符串，但是cin只会读取到空格为止，而cin.getline()会读取到回车为止。\\

\mybox{字符串输入输出}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	char str1[32];
	cout << "Enter string 1: ";
	cin.getline(str1, 32);
	cout << str1 << endl;

	char str2[32];
	cout << "Enter string 2: ";
	cin >> str2;
	cout << str2 << endl;

	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter string 1: hello world
hello world
Enter string 2: hello world
hello
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\mybox{字符统计}

\begin{lstlisting}[language=C++]
#include <iostream>

using namespace std;

int main() {
	char str[32];
	char c;

	cout << "Enter a string: ";
	cin.getline(str, 32);
	cout << "Character to search: ";
	cin >> c;

	int cnt = 0;
	int i = 0;
	while (str[i] != '\0') {
		if (str[i] == c) {
			cnt++;
		}
		i++;
	}

	cout << "'" << c << "' appears " << cnt << " times in \""
			<< str << "\"." << endl;
			
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter a string: this is a test
Character to search: t
't' appears 3 times in "this is a test".
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{字符串函数}

头文件<cstring>中定义了一些常用的字符串处理函数。

\subsubsection{strlen()}

计算字符串的长度。\\

\mybox{strlen()}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <cstring>

using namespace std;

int main() {
	char s[] = "hello world";
	cout << "Length: " << strlen(s) << endl;
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Length: 11
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsubsection{strcpy()}

字符串复制，调用者需要确保字符串的大小足够。\\

\mybox{strcpy()}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <cstring>

using namespace std;

int main() {
	char s1[32] = "hello world";
	char s2[32] = "program";

	strcpy(s1, s2);
	cout << "s1 = " << s1 << endl;
	cout << "s2 = " << s2 << endl;
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
s1 = program
s2 = program
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsubsection{strcat()}

字符串拼接，调用者需要确保字符串的大小足够。\\

\mybox{strcat()}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <cstring>

using namespace std;

int main() {
	char s1[32] = "hello";
	char s2[32] = "world";

	strcat(s1, s2);
	cout << "s1 = " << s1 << endl;
	cout << "s2 = " << s2 << endl;
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
s1 = helloworld
s2 = world
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsubsection{strcmp()}

字符串比较，依次比较字符串中每个字符的ASCII码值。通过判断strcmp()的返回值，可以得知两个字符串比较后的结果。

\begin{itemize}
	\item 负数：字符串1 < 字符串2
	\item 正数：字符串1 > 字符串2
	\item 0：字符串1 == 字符串2
\end{itemize}

\vspace{0.5cm}

\mybox{strcmp()}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <cstring>

using namespace std;

int main() {
	char s1[32] = "communication";
	char s2[32] = "compare";
	cout << strcmp(s1, s2) << endl;
	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
-1
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{字符串数组}

字符串数组是一个二维的字符数组，或者可以理解为是由多个字符串组成的数组。

\vspace{-0.5cm}

\begin{lstlisting}[language=C++]
char str[4][12] = {"C++", "Java", "Python", "JavaScript"};
\end{lstlisting}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{4mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			           & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3}      & \textbf{4}      & \textbf{5} & \textbf{6}      & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10}     & \textbf{11} \\
			\hline
			\textbf{0} & C          & +          & +          & $ \backslash $0 &                 &            &                 &            &            &            &                 &             \\
			\hline
			\textbf{1} & J          & a          & v          & a               & $ \backslash $0 &            &                 &            &            &            &                 &             \\
			\hline
			\textbf{2} & P          & y          & t          & h               & o               & n          & $ \backslash $0 &            &            &            &                 &             \\
			\hline
			\textbf{3} & J          & a          & v          & a               & S               & c          & r               & i          & p          & t          & $ \backslash $0 &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{lstlisting}[language=C++]
cout << "str[0] = " << str[0] << endl;			// C++
cout << "str[1] = " << str[1] << endl;			// Java
cout << "str[0][0] = " << str[0][0] << endl;	// C
cout << "str[0][1] = " << str[0][1] << endl;	// +
\end{lstlisting}

\newpage

\section{string}

\subsection{string}

string是一种字符串类型，使用时需要包含头文件<string>。\\

string提供了许多便捷的方法：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1mm}{
		\begin{tabular}{|l|l|}
			\hline
			\textbf{方法} & \textbf{功能}                           \\
			\hline
			length()      & 字符串长度                              \\
			\hline
			empty()       & 判断字符串是否为空                      \\
			\hline
			push\_back()  & 在字符串末尾添加字符                    \\
			\hline
			pop\_back()   & 删除字符串末尾的字符                    \\
			\hline
			append()      & 在字符串末尾添加字符串                  \\
			\hline
			insert()      & 在字符串指定位置处插入字符串            \\
			\hline
			erase()       & 删除字符串指定位置起n个字符             \\
			\hline
			replace()     & 替换字符串从指定位置起n个字符为新字符串 \\
			\hline
			substr()      & 获取字符串从指定位置起n个字符           \\
			\hline
			find()        & 查找字符串中是否存在指定字符串          \\
			\hline
			compare()     & 比较字符串和指定字符串的大小            \\
			\hline
		\end{tabular}
	}
	\caption{string常用方法}
\end{table}

\vspace{0.5cm}

\mybox{string方法}

\begin{lstlisting}[language=C++]
#include <iostream>
#include <string>

using namespace std;

int main() {
	string s = "Hello World!";
	cout << "length(): " << s.length() << endl;
	cout << "substr(): " << s.substr(0, 5) << endl;
	cout << "find(): " << s.find("World") << endl;

	s.push_back('!');
	cout << "push_back(): " << s << endl;

	s.pop_back();
	cout << "pop_back(): " << s << endl;

	s.append("Hello World!");
	cout << "append(): " << s << endl;

	s.insert(12, " ");
	cout << "insert(): " << s << endl;

	s.erase(13, 6);
	cout << "erase(): " << s << endl;

	s.replace(13, 5, "C++");
	cout << "replace(): " << s << endl;

	return 0;
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
length(): 12
empty(): 0
push_back(): Hello World!!
pop_back(): Hello World!
append(): Hello World!Hello World!
insert(): Hello World! Hello World!
erase(): Hello World! World!
replace(): Hello World! C++!
substr(): Hello
find(): 6
	\end{verbatim}
\end{tcolorbox}

\newpage